using System;
using System.Collections;

namespace RBT
{
    /// <summary>
    /// Returns the keys or data objects of the treap in sorted order
    /// </summary>
    public class RBTreeEnumerator
    {
        /// <summary>
        /// The treap uses the stack to order the nodes
        /// </summary>
        private Stack _stack;
        /// <summary>
        /// Return the keys
        /// </summary>
        private bool _keys;
        /// <summary>
        /// Return in _ascending order (true) or descending (false)
        /// </summary>
        private bool _ascending;
        public string Color;
        public IComparable ParentKey;
        /// <summary>
        /// Key
        /// </summary>
        public IComparable Key { get; set; }
        /// <summary>
        /// Data value
        /// </summary>
        public object Value { get; set; }
        /// <summary>
        /// Constructor
        /// </summary>
        public RBTreeEnumerator()
        {
        }
        /// <summary>
        /// Determine order, walk the tree and push the nodes onto the stack
        /// </summary>
        /// <param name="treeNode">Tree node</param>
        /// <param name="keys">Keys or not</param>
        /// <param name="ascending">Ascending or not</param>
        public RBTreeEnumerator(RBTreeNode treeNode, bool keys, bool ascending)
        {
            _stack = new Stack();
            _keys = keys;
            _ascending = ascending;
            // use depth-first traversal to push nodes into stack
            // the lowest next node will be at the top of the stack
            if (ascending)
            {   // find the lowest next node
                while (treeNode != RBTree.SentinelNode)
                {
                    _stack.Push(treeNode);
                    treeNode = treeNode.Left;
                }
            }
            else
            {
                // the highest next node will be at top of stack
                while (treeNode != RBTree.SentinelNode)
                {
                    _stack.Push(treeNode);
                    treeNode = treeNode.Right;
                }
            }
        }
        /// <summary>
        /// HasMoreElements
        /// </summary>
        /// <returns>True or False</returns>
        public bool HasMoreElements()
        {
            return (_stack.Count > 0);
        }
        /// <summary>
        /// NextElement
        /// </summary>
        /// <returns>Gets the next element</returns>
        public object NextElement()
        {
            if (_stack.Count == 0) 
                throw (new RBTreeException("Element not found"));
             //the top of stack will always have the next item
             //get top of stack but don't remove it as the next nodes 
             //in sequence may be pushed onto the top
             //the stack will be popped after all the nodes have been returned
            var nextNode = (RBTreeNode)_stack.Peek();   //next next node in sequence
            if (_ascending)//ascending
            {
                if (nextNode.Right == RBTree.SentinelNode)
                {
                    //top nextNode is lowest next node in subtree - pop next node off stack 
                    var treeNode = (RBTreeNode)_stack.Pop();
                    //peek at right next node's parent 
                    //get rid of it if it has already been used
                    while (HasMoreElements() && ((RBTreeNode)_stack.Peek()).Right == treeNode)
                        treeNode = (RBTreeNode)_stack.Pop();
                }
                else
                {
                    //find the next items in the sequence
                    //traverse to left; find lowest and push onto stack
                    var treeNode = nextNode.Right;
                    while (treeNode != RBTree.SentinelNode)
                    {
                        _stack.Push(treeNode);
                        treeNode = treeNode.Left;
                    }
                }
            }
            else//descending
            {
                if (nextNode.Left == RBTree.SentinelNode)
                {
                    //walk the tree
                    var treeNode = (RBTreeNode)_stack.Pop();
                    while (HasMoreElements() && ((RBTreeNode)_stack.Peek()).Left == treeNode)
                        treeNode = (RBTreeNode)_stack.Pop();
                }
                else
                {
                    //determine next next node in sequence
                    //traverse to left subtree and find greatest next node - push onto stack
                    var treeNode = nextNode.Left;
                    while (treeNode != RBTree.SentinelNode)
                    {
                        _stack.Push(treeNode);
                        treeNode = treeNode.Right;
                    }
                }
            }
            Key = nextNode.Key;
            Value = nextNode.Data;
            try
            {
                ParentKey = nextNode.Parent != null 
                    ? nextNode.Parent.Key : null;
            }
            catch (Exception e)
            {
                object ob = e;//stop compiler from complaining
                ParentKey = 0;
            }
            Color = nextNode.Color == 0 ? "Red" : "Black";
            return _keys ? nextNode.Key : nextNode.Data;
        }
        /// <summary>
        /// MoveNext
        /// </summary>
        /// <returns>True if there are more elements</returns>
        public bool MoveNext()
        {
            if (HasMoreElements())
            {
                NextElement();
                return true;
            }
            return false;
        }
    }
}